/**
 * @param {string[]} words
 * @return {string}
 */
var alienOrder = function (words) {
    const graph = {},
        inDegrees = {};
    for (let word of words) {
        for (let ch of word) {
            graph[ch] = {}; // 键保存起始节点  值里保存结束节点
            inDegrees[ch] = 0; // 入度都初始化 0
        }
    }
    for (let i = 1; i < words.length; i++) {
        // 构造图和入度 难点
        let w1 = words[i - 1];
        let w2 = words[i];
        if (w1.startsWith(w2) && w1.length !== w2.length) return ''; // 无论什么样的排序都是不可能的
        for (let j = 0; j < w1.length && j < w2.length; j++) {
            let ch1 = w1[j]; // 前面
            let ch2 = w2[j]; // 后面
            if (ch1 !== ch2) {
                if (!graph[ch1][ch2]) {
                    graph[ch1][ch2] = true; // 图中较小的字母指向较大的字母
                    ++inDegrees[ch2];
                }
                break; //终止 for 循环 因为顺序是按照前面的字母优先
            }
        }
    }
    const queue = []; // 找出图的拓扑排序即可
    for (let ch in inDegrees) if (inDegrees[ch] == 0) queue.push(ch);
    let res = '';
    while (queue.length) {
        let ch = queue.shift();
        res += ch;
        for (let next in graph[ch]) {
            --inDegrees[next];
            if (inDegrees[next] == 0) queue.push(next);
        }
    }
    return res.length === Object.keys(graph).length ? res : '';
};
